题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

概率重分配 & 拒绝采样

使用 rand7 生成10个同等概率的数字, 然后映射即可。

根据官方题解，我们可以调用两次 rand7 来生成等概率的[1,49]的数字, 只使用 [1，40]来作为rand10的采样, 如下图:

生成公式:

等概率的生成[1, X * Y]范围的随机数

• rand7() - 1 ==> 生成等概率的 {0,1,2,3,4,5,6} 其中一个
• (rand7() - 1)*7 ==> 生成等概率的 {0,7,14,21,28,35,42} 其中一个
• (rand7()-1)*7 + rand7() ==> 生成等概率的 [1,49] 其中一个

计算之后：

• 当出现 [1,40], 则转换成 [1,10] ==> sum%10 + 1
• 当出现 [41,49], 则重新生成

代码

var rand10 = function() {
    let sum = 0;
    do{
        sum = (rand7()-1)*7 + rand7()
    }while(sum>40)
    return 1+sum%10
};

参考资料

1. 470. 用 Rand7() 实现 Rand10() (opens new window)
2. 官方题解 (opens new window)
3. 从最基础的讲起如何做到均匀的生成随机数 (opens new window)